%
% Carátula oficial de 75.02 Algoritmos y Programación I, cátedra Cardozo.
%
% Basado en el template realizado por Diego Essaya, disponible en
%                                                         http://lug.fi.uba.ar
% Modificado por Michel Peterson.
% Modificado por Sebastián Santisi.
% Afando por Juan Antonio Zuloaga para el tp de Orga66.20
% lalala maxi

%
% Acá se define el tamaño de letra principal:
%
\documentclass[10pt]{article}

%------------------------- Carga de paquetes ---------------------------
%
% Si no necesitás algún paquete, comentalo.
%

%
% Definición del tamaño de página y los márgenes:
%
\usepackage[a4paper,headheight=16pt,scale={0.7,0.8},hoffset=0.5cm]{geometry}

%
% Vamos a escribir en castellano:
%
\usepackage[spanish]{babel}
%\usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}




%
% Si preferís el tipo de letra Helvetica (Arial), descomentá las siguientes
% dos lineas (las fórmulas seguirán estando en Times):
%
%\usepackage{helvet}
%\renewcommand\familydefault{\sfdefault}

%
% El paquete amsmath agrega algunas funcionalidades extra a las fórmulas. 
% Además defino la numeración de las tablas y figuras al estilo "Figura 2.3", 
% en lugar de "Figura 7". (Por lo tanto, aunque no uses fórmulas, si querés
% este tipo de numeración dejá el paquete amsmath descomentado).
%
\usepackage{amsmath}
\numberwithin{equation}{section}
\numberwithin{figure}{section}
\numberwithin{table}{section}

%
% Para tener cabecera y pie de página con un estilo personalizado:
%
\usepackage{fancyhdr}

%
% Para poner el texto "Figura X" en negrita:
% (Si no tenés el paquete 'caption2', probá con 'caption').
%
\usepackage[hang,bf]{caption2}

%
% Para poder usar subfiguras: (al estilo Figura 2.3(b) )
%
%\usepackage{subfigure}

%
% Para poder agregar notas al pie en tablas:
%
%\usepackage{threeparttable}

%------------------------------ graphicx ----------------------------------
%
% Para incluir imágenes, el siguiente código carga el paquete graphicx 
% según se esté generando un archivo dvi o un pdf (con pdflatex). 

% Para generar dvi, descomentá la linea siguiente:
%\usepackage[dvips]{graphicx}

% Para generar pdf, descomentá las dos lineas seguientes:
\usepackage[pdftex]{graphicx}
\pdfcompresslevel=9

\usepackage[final]{pdfpages}


%
% Todas las imágenes están en el directorio tp-img:
%
\newcommand{\imgdir}{includes}
\graphicspath{{\imgdir/}}
%
%------------------------------ graphicx ----------------------------------

% Necesitas este paquete si haces los diagrámas de flujo en el prográma Dia 
%\usepackage{tikz}


%------------------------- Inicio del documento ---------------------------

%
% Carátula:
%
% Título principal del documento.
\title{ \includegraphics[scale=0.3]{fiuba}
\\
\textbf{TRABAJO PRÁCTICO Nº2}
\\  Arquitecturas de Memoria}

% Información sobre los autores.
\author{Juan Antonio Zuloaga Mellino, \textit{Padrón Nro. 89.537}                     \\
            \texttt{ jzuloaga@fi.uba.ar }                                              \\
            Damián Ezequiel Moguilevsky, \textit{Padrón Nro. 90.174}                     \\
            \texttt{ dmoguilevsky@fi.uba.ar }                                              \\
            Maximiliano Gismondi, \textit{Padrón Nro. 89.957}                     \\
            \texttt{ maxig88@gmail.com }                                              \\
            \normalsize{ Año 2011 - 1\textsuperscript{er} Cuatrimestre}                       \\
            \normalsize{66.20 Organización de Computadoras}                             \\
            \normalsize{Facultad de Ingeniería, Universidad de Buenos Aires}            \\
       }
%\date{\today}
\date{} %Sin Fecha


\begin{document}

%
% Hago que en la cabecera de página se muestre a la derecha la sección,
% y en el pie, en número de página a la derecha:
%
\pagestyle{fancy}
\renewcommand{\sectionmark}[1]{\markboth{}{\thesection\ \ #1}}

\lhead{}
\chead{}
\rhead{\rightmark}
\lfoot{}
\cfoot{}
\rfoot{\thepage}



\begin{titlepage}

% Inserta el título.
\maketitle
\vfill
% Resumen
\begin{abstract}
En el presente trabajo práctico se aplicarán los conocimientos obtenidos, relativos a lo que se conoce como jerarquía de memorias, implementando una suite de benchmarking. Ésta permitirá medir 
parámetros de la memoria caché de datos. La implementación se realizó utilizando el lenguaje C y se separó en modulos de acuerdo al modelo propuesto por el enunciado.
\end{abstract}

\vfill
% Quita el número en la primer página.
\thispagestyle{empty}
\end{titlepage}


\newpage

%
% Hago que las páginas se comiencen a contar a partir de aquí:
%
\setcounter{page}{1}

%
% Pongo el índice en una página aparte:
\tableofcontents
\pagebreak
%
% Inicio del TP:
%
\section{Introducción}
\subsection{Necesidad de memorias caché}
A pesar del sorprendente crecimiento que tuvo a lo largo de los ultimos años la capacidad de la memoria principal en las computadoras personales, esta pieza de hardware sigue representando un
cuello de botella y por lo tanto es propensa a ser optimizada en busca de mejorar el rendimiento integral del equipo.

Esto se debe a que el aumento en el tamaño no fue acompañado por un aumento en la velocidad de acceso en similares proporciones sumado a que la brecha entre la frecuencia de operacion del microprocesador y la memoria principal se ha incrementando notablemente en los ultimos treinta años\cite{WIKI}, dando como resultado la necesidad de encontrar una solucion alternativa para que este problema no inhiba los desarrollos que se realizan sobre el resto del hardware.

Debido a la inviabilidad económica de tener memoria principal que funcione a la misma velocidad que el microprocesador, se optó por incluir un pequeño módulo de este tipo de memorias para contener sólo los datos que serán requeridos en el corto plazo, complementando asi a la lenta, abundante y económica memoria principal.

\subsection{Orientación del trabajo práctico}
Existen varias formas de organizar la memoria caché para optimizar su rendimiento. La aplicación desarrollada en el presente trabajo práctico permite obtener parámetros, a través de mediciones, de
la organización de la caché de datos perteneciente al equipo en donde se esta ejecutando. Dichos parámetros son: 

\begin{enumerate}
	\item[ ] Tamaño de bloque
	\item[ ] Cantidad de vías
	\item[ ] Tamaño total de la memoria caché analizada
\end{enumerate}

\section{Diseño}
La idea central para realizar las mediciones se basa en implementar el modelo del lazo simple, teniendo la posibilidad de variar la cantidad de accesos a memoria y obtener la tasa de miss para cada caso. En base a estos valores se calculan los parámetros requeridos.

La implementación del trabajo se realizó siguiendo el modelo modular aconsejado en el enunciado. Se implementaron tres módulos independientes para calcular respectivamente los tres parámetros mencionados en la sección anterior


\section{Implementación}
Para lograr una interfaz de usuario más amigable, se desarrolló un script en el que se invocan sucesivamente a los tres módulos anteriormente descriptos. Así también, se incorporó la necesidad de que el script compile los tres módulos para comprobar de esta manera que se cuenta con los fuentes de los módulos para poder modificar en tiempo de compilación los parámetros de entrada de cada uno de ellos. Además es el encargado de interpretar la salida de \textit{Cachegrind}.

A continuación se describen los cálculos empleados para obtener los parámetros que se esperan como resultado luego de ejecutar el programa.

\begin{enumerate}
	\item[ ] \textbf{Módulo de tamaño de bloque}: Para calcular el tamaño de bloque se accede a una determinada cantidad de memoria que debe ser potencia de dos. 
	
	Luego, usando Cachegrind, se obtiene la cantidad de misses que se produjeron en las lecturas. Con estos dos valores se calcula el tamaño de bloque usando la siguiente fórmula:
	\begin{center} $ TamBloque = \frac{Accesos}{Misses} $ \end{center}
	\item[ ] \textbf{Módulo de tamaño total de la memoria caché analizada}: Para determinar el tamaño total del caché analizado, $T$, se emplea el tamaño de bloque, $ {B} $, y se define ${M}$, un tamaño máximo posible de caché (En futuras implementaciones esto podría modificarse para permitir analizar cachés de tamaños superiores). En este caso, una vez definido ${M}$, se reserva esta cantidad de memoria. Luego, se comienza a iterar leyendo un dato por bloque de memoria. Esto se realiza con lazos de longitud ${L}$:
	\begin{center}${L=2^{n}\ \forall n \ \epsilon\ (0, log_{2}(M-B)) }$ \end{center}
	\item[ ] De esta manera a medida que se incrementa ${n}$ se itera sobre toda la memoria y finalmente se hace una lectura al primer elemento sobre el que se iteró. Y a partir de la salida del \textit{Cachegrind} se determina si la lectura resultó en un \textit{Miss} o un \textit{Hit}. Una vez completados todos los ciclos, se obtiene a partir de la cantidad de \textit{Misses} y de la cantidad de ciclos realizados el tamaño de la \textit{Caché}. Esto último, implica que:
	\begin{center}$Accesos\ a\ memoria\ -\ Ciclos_{Miss}\ =\ Ciclos_{Hit}$ \end{center}
	
	
	\begin{center}$T\ =\ 2^{Ciclos_{Hit}\ -\ 1}\ *\ B$\end{center}
	\item[ ] \textbf{Módulo de cantidad de vías}: Para realizar este cálculo, se necesita contar previamente con $B$ y $T$. Una vez que se cuenta con estos datos se reserva una cantidad predeterminada de memoria, $C$. Luego, suponiendo que la memoria tiene $N$ vías donde:
	\begin{center}$N = log_{2}(C)$\end{center} 
	Se realizan $N$ iteraciones, buscando determinar a partir de qué iteración, $i$, se obtiene una tasa de Miss del $100\%$. Indicando para este caso que la memoria cuenta con una asociatividad de $i$ vías.
\end{enumerate}

\section{Comandos para correr el programa}
El programa se compila y corre ejecutando un único comando desde la consola. El comando que debe ser ejecutado es el siguiente:
\\
\\
\noindent \texttt{
\$ ./launch
\\
\\
}

Luego de ejecutarlo se calcularán y mostrarán por salida estándar los parámetros calculados.

\section{Corridas de prueba}
A continuación se muestra la salida del programa, luego de ejecutar el comando indicado en la sección anterior.
\begin{figure}[!htb]
\begin{center}
\includegraphics[width=0.8\textwidth]{./includes/prueba1.png}
\end{center}
\caption{Salida del programa}
\end{figure}

\vfill

\begin{figure}[!htb]
\begin{center}
\includegraphics[width=0.8\textwidth]{./includes/ayuda.png}
\end{center}
\caption{Ayuda del programa}
\end{figure}

\vfill

\begin{figure}[!htb]
\begin{center}
\includegraphics[width=0.8\textwidth]{./includes/version.png}
\end{center}
\caption{Versión del programa}
\end{figure}

\vfill

\pagebreak

\section{Conclusión}
En la actualidad prácticamente todas las computadoras de escritorio poseen memoria caché. El uso de esta memoria mejora considerablemente el rendimiento de los equipos manteniendo un costo razonable.

El hecho de que sea tan usada incrementa la importancia de comprender su funcionamiento, para poder utilizarla adecuadamente.

En este trabajo práctico, usando las herramientas adecuadas y los conocimientos aprendidos en la materia, se pudieron estimar parámetros acerca del tamaño y organización de la memoria caché. Esta información puede ser muy útil para optimizar aplicaciones en función de la caché que se este usando logrando disminuir los tiempos de ejecución.

%\section{Bibliografía}
\begin{thebibliography}{99}
\bibitem{WIKI} CPU Cache history\\
http://en.wikipedia.org/wiki/CPU\_cache\#History
\end{thebibliography}


\appendix{}
\includepdf[pages={1,2,3}]{TP2-1C-2011}


\end{document}
